1. Field of the Invention
This invention relates to error detection and correction circuitry and the method employed thereby and more particularly to such circuitry and method for employment with shift register type memories.
2. Description of the Prior Art
The trend of memory organizations toward serial recirculating memories is increasing, not only because of the flexibility residing therein for storing variable length word sizes, but also because of the low costs resulting from minimal access and other overhead circuitry and also because of new component development. Thus, further memory systems particularly for bulk memories are anticipated to be formed of charge coupled devices (CCD) and magnetic bubble memories (magnetic domain memories) as well as MOS shift registers. In order to increase the storage capacity of such serial dynamic memories, a plurality of recirculating loops are provided when the data bits can only be accessed at fixed locations in the loops.
In order to increase the reliability of large memory systems, different error detection and error correction methods have been proposed and are described in the prior art. See, for example. R. T. Chien, "Memory Error Control; Beyond Parity," IEEE Spectrum, July 1973, pages 18-23. Among the more common of these methods have been parity check methods for random access memories such as cores and RAM semiconductor memories, and also cyclic redundancy codes (CRC) for serial memories (long shift registers) such as disks, drums and tapes.
Hamming codes have been commonly used to detect and correct errors. Information bits are appended with some code bits and are stored in the memory unit. When the information is retrieved, it is checked for being a code word. If the data is not a code word, then the minimum distance decoding is used for error correction.
Single bit parity, a degenerate case of Hamming code, can detect all single errors and some multiple errors. The value of the parity bit is determined to be zero or one depending on the number of zeros and ones in the information bits and whether even or odd parity is used. By using more than one bit to represent parity, multiple error detection and/or multiple error correction is possible. For multiple error detection, static and dynamic J-out-of-N checkers have been employed in the prior art. In all of these methods the costs in terms of the number of extra bits required for parity increases with increases in the number of errors to be detected and/or corrected.
It is desirable to increase the error correcting capability of a memory system without adding any extra bits to the memory and by using a minimal amount of extra logic. For example, a Hamming code capable of detecting and correcting "e" bit errors and detecting "e plus 1" bit errors can be upgraded to detect and correct "e plus 1" bit errors when such errors are of a burst mode type.
Predictions have been made that the most defects in shift register type memories, such as CCD's and magnetic bubble devices, will be such that all the bits in a given shift register are affected. Therefore, when a fault exists and a shift register affected by that fault is accessed, then burst error occurs. If the register is recirculated through enough cycles, then the error will propagate to all the bits in the shift register. Thus, a burst error equal to the shift register size is encountered. This error may generate all ones or all zeroes. It is expected that a large number of errors occurring in memory systems built with such recirculating memory devices will be of the burst error type.
It is then an object of the present invention to provide an improved error correcting circuit and method for a recirculating memory.
It is another object of the present invention to provide a more reliable and inexpensive error correcting circuit and method.
It is still another object of the present invention to provide an improved error correcting circuitry and method without requiring that extra bits be added to the existing error correction means and data segments.